package lib

import (
	"strconv"
	"strings"
)

//link to 241
func init() {
	Probs = append(Probs, Problem{
		Num:         8.14,
		Discription: "添加括号使得布尔表达式等于指定值的解法",
		Level:       3,
		Labels: map[string]int{
			"分治":    1,
			"回溯":    1,
			"记忆化搜索": 1,
			"动态规划": 1,
		},
	})
}

/*
两种思路：
1. n3动态规划
2. 回溯+记忆化搜索
*/

func CountEval2(s string, result int) int {
	if len(s) == 0 {
		return 0
	}

	if len(s) == 1 {
		if int(s[0]-'0') == result {
			return 1
		} else {
			return 0
		}
	}
	n := len(s)
	//dp[i][j][0,1]表示s[i:j+1]的表达式的值等于0,1的方案数
	dp := make([][][2]int, n)
	for i := range dp {
		dp[i] = make([][2]int, n)
	}

	for i := 0; i+2 < n; i += 2 {
		dp[i][i+2][cal(int(s[i]-'0'), int(s[i+2]-'0'), s[i+1])] = 1
		dp[i][i][int(s[i]-'0')] = 1
	}
	dp[n-1][n-1][int(s[n-1]-'0')] = 1

	for i := n - 5; i >= 0; i -= 2 {
		for j := i + 4; j < n; j += 2 {
			for opPos := i + 1; opPos <= j-1; opPos += 2 {
				//左、右边表达式为0或1的组合
				for left := 0; left <= 1; left++ {
					for right := 0; right <= 1; right++ {
						dp[i][j][cal(left, right, s[opPos])] += dp[i][opPos-1][left] * dp[opPos+1][j][right]
					}
				}
			}
		}
	}

	return dp[0][n-1][result]
}

func cal(x, y int, op byte) int {
	switch op {
	case '&':
		return x & y
	case '|':
		return x | y
	case '^':
		return x ^ y
	}

	return 0
}

//每次选一个运算符，递归计算左右两边表达式等于0和等于1的数量
func CountEval(s string, result int) int {
	cal := func(x, y int, op byte) string {

		res := 0
		switch op {
		case '&':
			res = x & y
		case '|':
			res = x | y
		case '^':
			res = x ^ y
		}

		if res == 0 {
			return "0"
		}

		return "1"
	}

	stateMap := make(map[[2]string]int, 0)
	var dfs func(string, string) int
	dfs = func(exp, target string) int {
		if len(exp) == 1 {
			if exp == target {
				return 1
			}

			return 0
		}

		if count, exist := stateMap[[2]string{exp, target}]; exist {
			return count
		}

		tempCount := 0
		for i := 1; i < len(exp); i += 2 {
			op := exp[i]
			for leftRes := 0; leftRes <= 1; leftRes++ {
				for rightRes := 0; rightRes <= 1; rightRes++ {
					if cal(leftRes, rightRes, op) == target {
						tempCount += dfs(exp[:i], strconv.Itoa(leftRes)) * dfs(exp[i+1:], strconv.Itoa(rightRes))
					}
				}
			}
		}

		stateMap[[2]string{exp, target}] = tempCount
		return tempCount
	}

	var numStrBuilder, opStrBuilder strings.Builder
	for i := 0; i < len(s); i++ {
		if s[i] == '0' || s[i] == '1' {
			numStrBuilder.WriteByte(s[i])
		} else {
			opStrBuilder.WriteByte(s[i])
		}
	}

	return dfs(s, strconv.Itoa(result))
}
